Scheda rapida Python-MIP

Questa scheda raccoglie in un unico posto tutto ciò che di Python-MIP serve nei laboratori e nella parte di programmazione dell’esame. Non introduce nulla di nuovo: ogni riga rimanda al capitolo in cui il costrutto è stato usato per la prima volta.

1. L’API essenziale#

Lo stato restituito da optimize() va controllato quando il modello potrebbe essere inammissibile: mip.OptimizationStatus.OPTIMAL indica che la soluzione è ottima, INFEASIBLE che non esistono soluzioni, UNBOUNDED che l’obiettivo può crescere senza limite. Leggere x.x su un modello inammissibile restituisce None.

2. Gli schemi che ricorrono#

Variabili indicizzate da un insieme di numeri consecutivi, in una lista (cap. 1):

x = [m.add_var(var_type=mip.INTEGER) for i in range(n)]

Variabili indicizzate da coppie, o da un insieme qualunque, in un dizionario (cap. 2):

f = {(i,j): m.add_var() for (i,j) in A}              # archi
x = {p: m.add_var() for p in P}                       # un sottoinsieme di indici

Una famiglia di vincoli, «per ogni $j$»: un ciclo for con dentro una xsum sull’altro indice.

for j in range(n_component):
    m.add_constr(mip.xsum(A[j][i]*x[i] for i in range(n_model)) <= b[j])

Somme filtrate, per esempio il flusso uscente e quello entrante in un nodo:

mip.xsum(f[i,j] for j in V if (i,j) in A) - mip.xsum(f[j,i] for j in V if (j,i) in A) == b[i]

Lettura di una soluzione binaria con una soglia, mai con == 1:

sol = [(i,j) for (i,j) in E if x[i,j].x > 0.5]

Una funzione che risolve il modello per dati diversi, che restituisce modello, soluzione e obiettivo (cap. 3):

def solve(A, b, c):
    m = mip.Model()
    x = [m.add_var() for j in range(len(c))]
    for i in range(len(b)):
        m.add_constr(mip.xsum(A[i][j]*x[j] for j in range(len(c))) <= b[i])
    m.objective = mip.maximize(mip.xsum(c[j]*x[j] for j in range(len(c))))
    m.optimize()
    return m, [v.x for v in x], m.objective_value

Aggiungere vincoli a posteriori e riottimizzare (tagli di subtour elimination, cap. 2):

while esiste_un_vincolo_violato(sol):
    m.add_constr(...)
    m.optimize()

Dati che vanno copiati prima di essere modificati: b3 = b[:] crea una copia; b3 = b crea solo un secondo nome per la stessa lista, e modificare b3 modifica anche b.

3. La scaletta di modellazione#

Da ripetere identica per ogni problema, prima di scrivere una riga di codice.

1. Insiemi: di che cosa si parla (prodotti, risorse, nodi, archi, periodi). Ogni insieme diventa un range o una lista.
2. Parametri: tutti i numeri del testo, e solo quelli, con l’indice giusto ($c_i$, $a_{ji}$, $b_j$). Lettere iniziali dell’alfabeto.
3. Variabili decisionali: che cosa si decide, con che indice e di che natura (continua, intera, binaria). Lettere finali dell’alfabeto.
4. Obiettivo: una sola espressione lineare, da massimizzare o minimizzare.
5. Vincoli: una famiglia per ogni «per ogni» del testo; per ognuna, quale indice è fissato e su quale corre la somma.
6. Traduzione: dati, Model(), variabili, vincoli, obiettivo, optimize(), stampa. Poi verifica a mano che la soluzione rispetti i vincoli.

4. Errori tipici#

5. Glossario#

Sintesi trasversale dei capitoli 1, 2 e 3: da tenere aperta mentre si scrive un modello.